package com.pan.alg.leecode;

/**
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * 注意：给定 n 是一个正整数。
 * @author by panstark
 * @description
 * @notice
 * @date 2021/8/4
 */
public class Leecode70 {


    int[] memo1 ;


    /**
     * 通过递归方式调用
     * @param n
     * @return
     */
    public int climb1(int n){

        memo1 = new int[n+1];

        return calculate1(n);
    }

    private int calculate1(int n) {

        if(n==0){
            return 1;
        }
        if(n==1){
            return 1;
        }

        if(memo1[n]==0){
            memo1[n]=calculate1(n-1)+calculate1(n-2);
        }
        return memo1[n];
    }

    /**
     * 动态规划的核心原理
     * 将一个大问题划分为若干小问题，通过解决小问题，来解决大问题。
     * 在爬楼梯中，可以看到有一个台阶时，有一种可能。有两个台阶时，有两种可能。
     * 三个台阶，就有最后一步迈两个台阶和迈一个台阶的可能。
     * @param n
     * @return
     */
    public int climb2(int n){

        int[] memo2 = new int[n+1];
        memo2[0]=1;
        memo2[1]=1;
        for (int i = 2; i <n+1 ; i++) {
            memo2[i]=memo2[i-1]+memo2[i-2];
        }
        return memo2[n];
    }

}
